package backtracking;

import java.util.ArrayList;
import java.util.List;

public class CombinationSumiii216 {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        backtracing(1, k, n, new ArrayList<>(), result);
        return result;
    }

    private void backtracing(int c, int k, int n, List<Integer> cur, List<List<Integer>> result) {

        if (cur.size() == k) {
            int sum = 0;
            for (int i = 0; i < cur.size(); i++) {
                sum += cur.get(i);
            }
            if (sum == n) {
                result.add(new ArrayList<>(cur));
            }
            return;
        }
        if (c > 9) {
            return;
        }
        cur.add(c);
        backtracing(c + 1, k, n, cur, result);
        cur.remove(cur.size() - 1);
        backtracing(c + 1, k, n, cur, result);
    }
}
